﻿#include <string>
#include <algorithm>
#include <iostream>

using namespace std;


/*
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0
 

提示：
0 <= s.length <= 3 * 10^4
s[i] 为 '(' 或 ')'
*/




class Solution {
public:
	int longestValidParentheses(string s) {
		if (s.empty()) return 0;
		int dp[30010] = { 0 };
		for (int i = 0; i < s.size(); i++) {
			if (i > 0 && s[i] == ')') {
				if (s[i - 1] == '(') {
					dp[i] = 2;
					if (i>=2 && s[i - 2] == ')') {
						dp[i] += dp[i - 2];
					}
				}
				else if (s[i - 1] == ')') {
					int t = dp[i - 1];
					if ((i - 1 - t>=0) && s[i - 1 - t] == '(') {
						dp[i] = t + 2;
						if (i - 2 - t >= 0 && s[i - 2 - t] == ')') {
							dp[i] += dp[i - 2 - t];
						}
					}
				}
			}
		}
		int ans = -99;
		for (int i = 0; i < s.size(); i++) {
			ans = max(ans, dp[i]);
		}

		return ans;
	}
};




//int main() {
//	Solution s;
//	cout << s.longestValidParentheses("(()())") << endl;;
//
//	return 0;
//}